/*******************************************************************************
* FileName:         MyString.cpp
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/10/30 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #5
*                   完成程度：
*                   全部完成，并编写了kmp的依赖函数buildLPSArray（）
*******************************************************************************/
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include "MyString.h"

// 构造函数
MyString::MyString(const char* input) {
    len = strlen(input); // 使用自定义的strlen函数
    str = new char[len + 1]; // 分配内存
    copystr(str, input, len); // 复制字符串
}

// 析构函数
MyString::~MyString() {
    delete[] str; // 释放内存
}

// 返回字符串长度
int MyString::length() const {
    return len; // 返回字符串长度
}

// 替换字符串
void MyString::replace(const char* replace, int loc) {
    if (loc < 0 || loc > len) return; // 修改为 loc <= len，允许在末尾替换

    int newstr_len = strlen(replace); // 新字符串的长度
    // 计算替换后总长度：原字符串的长度 - 被替换部分的长度 + 新字符串的长度
    int total_len = len - (len - loc) + newstr_len;

    char* temp = new char[total_len + 1]; // 新内存分配

    // 复制原字符串的前半部分
    for (int i = 0; i < loc; i++) {
        temp[i] = str[i];
    }

    // 复制替换的字符串
    copystr(temp + loc, replace, newstr_len);

    // 复制原字符串替换位置后的部分
    for (int i = loc; i < len; i++) {
        temp[i + newstr_len] = str[i];
    }

    // 结束字符
    temp[total_len] = '\0';

    // 释放原字符串内存
    delete[] str;
    str = temp; // 更新字符串指针
    len = total_len; // 更新长度
}



// 构建KMP算法的部分匹配表（LPS表）
void MyString::buildLPSArray(const char* pattern, int patternLen, int* lps) const{
    int lenn = 0; // LPS长度
    lps[0] = 0; // 第一个元素总是0
    int i = 1;

    while (i < patternLen) {
        if (pattern[i] == pattern[lenn]) {
            lenn++;
            lps[i] = lenn;
            i++;
        } else {
            if (lenn != 0) {
                lenn = lps[lenn - 1]; // 使用之前的LPS
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// 查找子串
int MyString::find(const char* substr) const {
    int sublen = strlen(substr); // 子串长度
    if (sublen == 0 || sublen > len) {
        return -1; // 如果子串为空或比原字符串长，返回-1
    }

    int* lps = new int[sublen]; // LPS数组
    buildLPSArray(substr, sublen, lps); // 构建LPS数组

    int i = 0; // 主字符串索引
    int j = 0; // 子串索引
    while (i < len) {
        if (str[i] == substr[j]) {
            i++;
            j++;
        }
        if (j == sublen) { // 找到匹配
            delete[] lps; // 释放LPS内存
            return i - j; // 返回匹配开始的索引
        } else if (i < len && str[i] != substr[j]) {
            if (j != 0) {
                j = lps[j - 1]; // 使用LPS数组
            } else {
                i++;
            }
        }
    }

    delete[] lps; // 释放LPS内存
    return -1; // 未找到
}

// 返回C语言风格字符串
const char* MyString::c_string() const {
    return str; // 返回内部字符串
}

void MyString::showstr(){
    std :: cout << str;
}
